package arithmetic.demo7;


import java.util.*;


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

/**
 * 题目： 交易逆序对的总数
 *
 * 方法： 小找大
 */
class Solution2 {
    public int reversePairs(int[] record) {
        
        // 归并查找
       return memrcySearch(record, 0,record.length-1);
    }

    private int memrcySearch(int[] nums, int begin, int end) {

        // 递归出口
        if(begin >= end) {
            return 0;
        }


        int ret = 0;

        int mid = (end + begin) / 2;
        // 左： [begin, mid] 右： [mid+1, end]

        // 左区间寻找
        // for(int i = begin; i <= mid; i++) {
        //     for(int j = i + 1; j <= mid; j++) {
        //         if(nums[i] > nums[j]) {
        //             ret++;
        //         }
        //     }
        // }

        // 左区间排序
       ret += memrcySearch(nums, begin, mid);


        //右区间寻找
        // for(int i = mid+1; i <= end; i++) {
        //     for(int j = i + 1; j <= end; j++) {
        //         if(nums[i] > nums[j]) {
        //             ret++;
        //         }
        //     }
        // }

        // 右区间排序
       ret +=  memrcySearch(nums, mid + 1, end);

        int cur1 = begin, cur2 = mid+1;

        // // 两边查找
        // while(cur1 <= mid && cur2 <= end) {
        //     if(nums[cur1] > nums[cur2]) {
        //         ret  += (mid - cur1) + 1;
        //         cur2++;
        //     } else {
        //         cur1++;
        //     }
        // }

        // // 开始排序
        // cur1 = begin; cur2 = mid +1;


        int  i = 0;
        int[] tmp = new int[end - begin + 1];
        while(cur1 <= mid && cur2 <= end) {
            if(nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }


        while(cur1 <= mid) {
            tmp[i++] = nums[cur1++]; 
        } 

        while(cur2 <= end) {
            tmp[i++] = nums[cur2++];
        }

        // 拷贝回去
        for(int j = begin; j <= end ; j++) {
            nums[j] = tmp[j - begin]; 
        }

   
        return ret;

    }
}


/**
 * 题目： 交易逆序对的总数
 *
 * 方法： 小找大
 *
 */


class Solution1 {
    public int reversePairs(int[] record) {

        // 归并查找
        return memrcySearch(record, 0,record.length-1);
    }

    private int memrcySearch(int[] nums, int begin, int end) {

        // 递归出口
        if(begin >= end) {
            return 0;
        }


        int ret = 0;

        int mid = (end + begin) / 2;
        // 左： [begin, mid] 右： [mid+1, end]



        // 左区间寻找并排序
        ret += memrcySearch(nums, begin, mid);




        // 右区间寻找并排序
        ret +=  memrcySearch(nums, mid + 1, end);

        int cur1 = begin, cur2 = mid+1;

        // // 两边查找
        // while(cur1 <= mid && cur2 <= end) {
        //     if(nums[cur1] > nums[cur2]) {
        //         ret  += (mid - cur1) + 1;
        //         cur2++;
        //     } else {
        //         cur1++;
        //     }
        // }

        // // 开始排序
        // cur1 = begin; cur2 = mid +1;


        int  i = 0;
        int[] tmp = new int[end - begin + 1];
        while(cur1 <= mid && cur2 <= end) {
            if(nums[cur1] > nums[cur2]) {
                ret += end - cur2 + 1;
                tmp[i++] = nums[cur1++];
            } else {
                tmp[i++] = nums[cur2++];
            }
        }


        while(cur1 <= mid) {
            tmp[i++] = nums[cur1++];
        }

        while(cur2 <= end) {
            tmp[i++] = nums[cur2++];
        }

        // 拷贝回去
        for(int j = begin; j <= end ; j++) {
            nums[j] = tmp[j - begin];
        }


        return ret;

    }
}


/**
 * 题目: 分治_归并_计算右侧小于当前元素的个数
 */

class Solution {
    int[] index ;
    int[] ret;
    public List<Integer> countSmaller(int[] nums) {
        // 初始化
        int n = nums.length;
        List<Integer> ph = new ArrayList<>();
        index = new int[n];
        ret = new int[n];

        for(int i =0; i < n ;i++) {
            index[i] = i;
        }

        mercySearch(nums, 0, n-1);


        for(int i =0; i<n; i++) {
            ph.add(ret[i]);
        }

        return ph;

    }

    public void mercySearch(int[] nums, int left , int right) {

        // 递归出口
        if(left >= right) {
            return ;
        }

        int mid = (right + left) / 2;

        // 左区域
        mercySearch(nums, left , mid);

        // 右区域
        mercySearch(nums, mid + 1, right );

        int cur1 = left , cur2 = mid + 1 ;

        int[] indexTmp = new int[right - left + 1];
        int[] tmp = new int[right - left + 1];
        int i = 0;
        // 开始排序
        while(cur1 <= mid && cur2 <= right) {
            if(nums[cur1] > nums[cur2]) {
                ret[index[cur1]] += (right - cur2 + 1);
                indexTmp[i] = index[cur1];
                tmp[i++] = nums[cur1++];
            } else {
                indexTmp[i] = index[cur2];
                tmp[i++] = nums[cur2++];
            }
        }

        while(cur1 <= mid) {
            indexTmp[i] = index[cur1];
            tmp[i++] = nums[cur1++];
        }

        while(cur2 <= right) {
            indexTmp[i] = index[cur2];
            tmp[i++] = nums[cur2++];
        }


        // 拷贝回去
        for(int  j = left; j <= right ; j++) {
            index[j] = indexTmp[j - left];
            nums[j]= tmp[j - left];
        }



    }
}

/**
 * 题目： 分治_归并_翻转对
 */

class Solution3 {

    public int reversePairs(int[] nums) {
        return  mercySort(nums, 0, nums.length-1);
    }


    public int mercySort(int[] nums , int begin , int end) {
        // 递归出口
        if(begin >= end) {
            return 0;
        }

        int ret  = 0;
        int mid = (end + begin)/2;
        // [begin, mid] [mid + 1, end];
        ret += mercySort(nums, begin, mid);
        ret += mercySort(nums , mid + 1, end);

        // 先统计个数
        int[] tmp = new int[end - begin + 1];
        int cur1 = begin, cur2 = mid + 1, index = 0;
        while(cur1 <= mid && cur2 <= end) {
            // 加入结果
            if( (nums[cur1] / 2.0) > ( nums[cur2])) {
                ret += mid - cur1 + 1;
                cur2++;
            } else {
                cur1++;
            }
        }


        cur1 = begin ; cur2 = mid + 1 ;

        while(cur1 <= mid && cur2 <= end) {
            if(nums[cur1] <= nums[cur2]) {
                tmp[index++] = nums[cur1++];
            } else {
                // 加入结果
                tmp[index++] = nums[cur2++];
            }
        }


        // 处理剩余数据
        while(cur1 <= mid) {
            tmp[index++] = nums[cur1++];
        }

        while(cur2 <= end) {
            tmp[index++] = nums[cur2++];
        }

        // 讲临时数据拷贝回来
        for(int i = begin ; i<= end ; i++) {
            nums[i]= tmp[i- begin];
        }


        return ret;
    }

}



